// hard

// N个孩子站成一排，老师会根据每个孩子的表现，给每个孩子进行评分，然后根据下面的规则给孩子们分发糖果
// 1. 每个孩子至少得一个糖果
// 2. 评分更高的孩子必须比他两侧相邻位置上的孩子分得更多的糖果

// 现在给定N个孩子的表现分数数组ratings，要求返回最少需要准备的糖果数目

// 解题思路
// 每个孩子至少一个糖果，说明糖果数目至少为N个
// 评分更高的孩子必须比他两侧相邻位置上的孩子分得更多的糖果,可以看做以下两种条件：
// 1. 当ratings[i-1] < ratings[i]时，第i个孩子的糖果数量比第i-1个孩子的糖果数量多
// 2. 当ratings[i] > ratings[i+1]时， 第i个孩子的糖果数量比第i+1个孩子的糖果数量多

// 我们可以设定一个长度为N的数组sweets来表示每个孩子分得的最少糖果数，初始每个孩子分得糖果数都为1
// 然后遍历两遍数组，第一遍遍历满足当ratings[i-1] < ratings[i]时，第i个孩子的糖果数量比第i-1个孩子的糖果数量多
// 第二遍遍历满足当ratings[i] > ratings[i+1]时， 第i个孩子的糖果数量比第i+1个孩子的糖果数量多
// 然后再遍历所有孩子的糖果数量和即为答案

function candy(ratings) {
    let size = ratings.length
    let sweets = new Array(size).fill(1)

    for (let i = 1; i < size; i++) {
        if (ratings[i] > ratings[i - 1]) {
            sweets[i] = sweets[i - 1] + 1
        }
    }

    for (let i = size - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            sweets[i] = Math.max(sweets[i], sweets[i + 1] + 1)
        }
    }
    let res = 0
    for (let i = 0; i < sweets.length; i++) {
        res +=  sweets[i]
    }
    return res
}

let ratings = [1,0,2]
console.log(candy(ratings))
